

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>federatedml.feature.quantile_summaries &mdash; FATE 1.0 documentation</title>
  

  
  
  
  

  
  <script type="text/javascript" src="../../../_static/js/modernizr.min.js"></script>
  
    
      <script type="text/javascript" id="documentation_options" data-url_root="../../../" src="../../../_static/documentation_options.js"></script>
        <script type="text/javascript" src="../../../_static/jquery.js"></script>
        <script type="text/javascript" src="../../../_static/underscore.js"></script>
        <script type="text/javascript" src="../../../_static/doctools.js"></script>
        <script type="text/javascript" src="../../../_static/language_data.js"></script>
    
    <script type="text/javascript" src="../../../_static/js/theme.js"></script>

    

  
  <link rel="stylesheet" href="../../../_static/css/theme.css" type="text/css" />
  <link rel="stylesheet" href="../../../_static/pygments.css" type="text/css" />
    <link rel="index" title="Index" href="../../../genindex.html" />
    <link rel="search" title="Search" href="../../../search.html" /> 
</head>

<body class="wy-body-for-nav">

   
  <div class="wy-grid-for-nav">
    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search" >
          

          
            <a href="../../../index.html" class="icon icon-home"> FATE
          

          
          </a>

          
            
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="../../../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
              
            
            
              <!-- Local TOC -->
              <div class="local-toc"></div>
            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" aria-label="top navigation">
        
          <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
          <a href="../../../index.html">FATE</a>
        
      </nav>


      <div class="wy-nav-content">
        
        <div class="rst-content">
        
          















<div role="navigation" aria-label="breadcrumbs navigation">

  <ul class="wy-breadcrumbs">
    
      <li><a href="../../../index.html">Docs</a> &raquo;</li>
        
          <li><a href="../../index.html">Module code</a> &raquo;</li>
        
      <li>federatedml.feature.quantile_summaries</li>
    
    
      <li class="wy-breadcrumbs-aside">
        
      </li>
    
  </ul>

  
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <h1>Source code for federatedml.feature.quantile_summaries</h1><div class="highlight"><pre>
<span></span><span class="ch">#!/usr/bin/env python</span>
<span class="c1"># -*- coding: utf-8 -*-</span>

<span class="c1">#</span>
<span class="c1">#  Copyright 2019 The FATE Authors. All Rights Reserved.</span>
<span class="c1">#</span>
<span class="c1">#  Licensed under the Apache License, Version 2.0 (the &quot;License&quot;);</span>
<span class="c1">#  you may not use this file except in compliance with the License.</span>
<span class="c1">#  You may obtain a copy of the License at</span>
<span class="c1">#</span>
<span class="c1">#      http://www.apache.org/licenses/LICENSE-2.0</span>
<span class="c1">#</span>
<span class="c1">#  Unless required by applicable law or agreed to in writing, software</span>
<span class="c1">#  distributed under the License is distributed on an &quot;AS IS&quot; BASIS,</span>
<span class="c1">#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.</span>
<span class="c1">#  See the License for the specific language governing permissions and</span>
<span class="c1">#  limitations under the License.</span>
<span class="c1">#</span>

<span class="kn">import</span> <span class="nn">math</span>

<span class="kn">from</span> <span class="nn">federatedml.util</span> <span class="k">import</span> <span class="n">consts</span>


<div class="viewcode-block" id="Stats"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.Stats">[docs]</a><span class="k">class</span> <span class="nc">Stats</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">value</span><span class="p">,</span> <span class="n">g</span><span class="p">:</span> <span class="nb">int</span><span class="p">,</span> <span class="n">delta</span><span class="p">:</span> <span class="nb">int</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="n">value</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">g</span> <span class="o">=</span> <span class="n">g</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">delta</span> <span class="o">=</span> <span class="n">delta</span></div>


<div class="viewcode-block" id="QuantileSummaries"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.QuantileSummaries">[docs]</a><span class="k">class</span> <span class="nc">QuantileSummaries</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">compress_thres</span><span class="o">=</span><span class="n">consts</span><span class="o">.</span><span class="n">DEFAULT_COMPRESS_THRESHOLD</span><span class="p">,</span>
                 <span class="n">head_size</span><span class="o">=</span><span class="n">consts</span><span class="o">.</span><span class="n">DEFAULT_HEAD_SIZE</span><span class="p">,</span>
                 <span class="n">error</span><span class="o">=</span><span class="n">consts</span><span class="o">.</span><span class="n">DEFAULT_RELATIVE_ERROR</span><span class="p">,</span>
                 <span class="n">abnormal_list</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">compress_thres</span> <span class="o">=</span> <span class="n">compress_thres</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">head_size</span> <span class="o">=</span> <span class="n">head_size</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">error</span> <span class="o">=</span> <span class="n">error</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">head_sampled</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span> <span class="o">=</span> <span class="p">[]</span>  <span class="c1"># list of Stats</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">count</span> <span class="o">=</span> <span class="mi">0</span>  <span class="c1"># Total observations appeared</span>
        <span class="k">if</span> <span class="n">abnormal_list</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">abnormal_list</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">abnormal_list</span> <span class="o">=</span> <span class="n">abnormal_list</span>

    <span class="c1"># insert a number</span>
<div class="viewcode-block" id="QuantileSummaries.insert"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.QuantileSummaries.insert">[docs]</a>    <span class="k">def</span> <span class="nf">insert</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Insert an observation of data. First store in a array buffer. If the buffer is full,</span>
<span class="sd">        do a batch insert. If the size of sampled list reach compress_thres, compress this list.</span>
<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        x : float</span>
<span class="sd">            The observation that prepare to insert</span>

<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="n">x</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">abnormal_list</span><span class="p">:</span>
            <span class="k">return</span>

        <span class="k">try</span><span class="p">:</span>
            <span class="n">x</span> <span class="o">=</span> <span class="nb">float</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>
        <span class="k">except</span> <span class="ne">ValueError</span><span class="p">:</span>
            <span class="k">return</span>

        <span class="bp">self</span><span class="o">.</span><span class="n">head_sampled</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">head_sampled</span><span class="p">)</span> <span class="o">&gt;=</span> <span class="bp">self</span><span class="o">.</span><span class="n">head_size</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_insert_head_buffer</span><span class="p">()</span>
            <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">)</span> <span class="o">&gt;=</span> <span class="bp">self</span><span class="o">.</span><span class="n">compress_thres</span><span class="p">:</span>
                <span class="bp">self</span><span class="o">.</span><span class="n">compress</span><span class="p">()</span></div>

    <span class="k">def</span> <span class="nf">_insert_head_buffer</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">head_sampled</span><span class="p">):</span>  <span class="c1"># If empty</span>
            <span class="k">return</span>
        <span class="n">current_count</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">count</span>
        <span class="n">sorted_head</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">head_sampled</span><span class="p">)</span>
        <span class="n">new_sampled</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="n">sample_idx</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="n">ops_idx</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="k">while</span> <span class="n">ops_idx</span> <span class="o">&lt;</span> <span class="nb">len</span><span class="p">(</span><span class="n">sorted_head</span><span class="p">):</span>
            <span class="n">current_sample</span> <span class="o">=</span> <span class="n">sorted_head</span><span class="p">[</span><span class="n">ops_idx</span><span class="p">]</span>
            <span class="k">while</span> <span class="n">sample_idx</span> <span class="o">&lt;</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">)</span> <span class="ow">and</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="n">sample_idx</span><span class="p">]</span><span class="o">.</span><span class="n">value</span> <span class="o">&lt;=</span> <span class="n">current_sample</span><span class="p">:</span>
                <span class="n">new_sampled</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="n">sample_idx</span><span class="p">])</span>
                <span class="n">sample_idx</span> <span class="o">+=</span> <span class="mi">1</span>

            <span class="n">current_count</span> <span class="o">+=</span> <span class="mi">1</span>

            <span class="c1"># If it is the first one to insert or if it is the last one</span>
            <span class="k">if</span> <span class="ow">not</span> <span class="n">new_sampled</span> <span class="ow">or</span> <span class="p">(</span><span class="n">sample_idx</span> <span class="o">==</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">)</span> <span class="ow">and</span>
                                           <span class="n">ops_idx</span> <span class="o">==</span> <span class="nb">len</span><span class="p">(</span><span class="n">sorted_head</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span><span class="p">):</span>
                <span class="n">delta</span> <span class="o">=</span> <span class="mi">0</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="n">delta</span> <span class="o">=</span> <span class="n">math</span><span class="o">.</span><span class="n">floor</span><span class="p">(</span><span class="mi">2</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">error</span> <span class="o">*</span> <span class="n">current_count</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span>

            <span class="n">new_stats</span> <span class="o">=</span> <span class="n">Stats</span><span class="p">(</span><span class="n">current_sample</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="n">delta</span><span class="p">)</span>
            <span class="n">new_sampled</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">new_stats</span><span class="p">)</span>
            <span class="n">ops_idx</span> <span class="o">+=</span> <span class="mi">1</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span> <span class="o">=</span> <span class="n">new_sampled</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">head_sampled</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">count</span> <span class="o">=</span> <span class="n">current_count</span>

<div class="viewcode-block" id="QuantileSummaries.compress"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.QuantileSummaries.compress">[docs]</a>    <span class="k">def</span> <span class="nf">compress</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_insert_head_buffer</span><span class="p">()</span>
        <span class="n">merge_threshold</span> <span class="o">=</span> <span class="n">math</span><span class="o">.</span><span class="n">floor</span><span class="p">(</span><span class="mi">2</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">error</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">count</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span>
        <span class="n">compressed</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_compress_immut</span><span class="p">(</span><span class="n">merge_threshold</span><span class="p">)</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span> <span class="o">=</span> <span class="n">compressed</span></div>

<div class="viewcode-block" id="QuantileSummaries.merge"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.QuantileSummaries.merge">[docs]</a>    <span class="k">def</span> <span class="nf">merge</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        merge current summeries with the other one.</span>
<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        other : QuantileSummaries</span>
<span class="sd">            The summaries to be merged</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="n">other</span><span class="o">.</span><span class="n">head_sampled</span><span class="p">:</span>
            <span class="n">other</span><span class="o">.</span><span class="n">_insert_head_buffer</span><span class="p">()</span>

        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">head_sampled</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_insert_head_buffer</span><span class="p">()</span>

        <span class="k">if</span> <span class="n">other</span><span class="o">.</span><span class="n">count</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span>

        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">count</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">other</span>

        <span class="c1"># merge two sorted array</span>
        <span class="n">new_sample</span> <span class="o">=</span> <span class="p">[]</span>
        <span class="n">i</span><span class="p">,</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span>
        <span class="k">while</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">)</span> <span class="ow">and</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="nb">len</span><span class="p">(</span><span class="n">other</span><span class="o">.</span><span class="n">sampled</span><span class="p">):</span>
            <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">.</span><span class="n">value</span> <span class="o">&lt;</span> <span class="n">other</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">.</span><span class="n">value</span><span class="p">:</span>
                <span class="n">new_sample</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
                <span class="n">i</span> <span class="o">+=</span> <span class="mi">1</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="n">new_sample</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">other</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="n">j</span><span class="p">])</span>
                <span class="n">j</span> <span class="o">+=</span> <span class="mi">1</span>
        <span class="n">new_sample</span> <span class="o">+=</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="n">i</span><span class="p">:]</span>
        <span class="n">new_sample</span> <span class="o">+=</span> <span class="n">other</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="n">j</span><span class="p">:]</span>

        <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span> <span class="o">=</span> <span class="n">new_sample</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">count</span> <span class="o">+=</span> <span class="n">other</span><span class="o">.</span><span class="n">count</span>
        <span class="n">merge_threshold</span> <span class="o">=</span> <span class="n">math</span><span class="o">.</span><span class="n">floor</span><span class="p">(</span><span class="mi">2</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">error</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">count</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_compress_immut</span><span class="p">(</span><span class="n">merge_threshold</span><span class="p">)</span></div>

<div class="viewcode-block" id="QuantileSummaries.query"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.QuantileSummaries.query">[docs]</a>    <span class="k">def</span> <span class="nf">query</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">quantile</span><span class="p">):</span>
        <span class="sd">&quot;&quot;&quot;</span>
<span class="sd">        Given the queried quantile, return the approximation guaranteed result</span>
<span class="sd">        Parameters</span>
<span class="sd">        ----------</span>
<span class="sd">        quantile : float [0.0, 1.0]</span>
<span class="sd">            The target quantile</span>

<span class="sd">        Returns</span>
<span class="sd">        -------</span>
<span class="sd">        float, the corresponding value result.</span>
<span class="sd">        &quot;&quot;&quot;</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">head_sampled</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">_insert_head_buffer</span><span class="p">()</span>

        <span class="k">if</span> <span class="n">quantile</span> <span class="o">&lt;</span> <span class="mi">0</span> <span class="ow">or</span> <span class="n">quantile</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span>
            <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s2">&quot;Quantile should be in range [0.0, 1.0]&quot;</span><span class="p">)</span>

        <span class="k">if</span> <span class="n">quantile</span> <span class="o">&lt;=</span> <span class="bp">self</span><span class="o">.</span><span class="n">error</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">value</span>

        <span class="k">if</span> <span class="n">quantile</span> <span class="o">&gt;=</span> <span class="mi">1</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">error</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">.</span><span class="n">value</span>

        <span class="n">rank</span> <span class="o">=</span> <span class="n">math</span><span class="o">.</span><span class="n">ceil</span><span class="p">(</span><span class="n">quantile</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">count</span><span class="p">)</span>
        <span class="n">target_error</span> <span class="o">=</span> <span class="n">math</span><span class="o">.</span><span class="n">ceil</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">error</span> <span class="o">*</span> <span class="bp">self</span><span class="o">.</span><span class="n">count</span><span class="p">)</span>
        <span class="n">min_rank</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span>
        <span class="k">while</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span><span class="p">:</span>
            <span class="n">cur_sample</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
            <span class="n">min_rank</span> <span class="o">+=</span> <span class="n">cur_sample</span><span class="o">.</span><span class="n">g</span>
            <span class="n">max_rank</span> <span class="o">=</span> <span class="n">min_rank</span> <span class="o">+</span> <span class="n">cur_sample</span><span class="o">.</span><span class="n">delta</span>
            <span class="k">if</span> <span class="n">max_rank</span> <span class="o">-</span> <span class="n">target_error</span> <span class="o">&lt;=</span> <span class="n">rank</span> <span class="o">&lt;=</span> <span class="n">min_rank</span> <span class="o">+</span> <span class="n">target_error</span><span class="p">:</span>
                <span class="k">return</span> <span class="n">cur_sample</span><span class="o">.</span><span class="n">value</span>
            <span class="n">i</span> <span class="o">+=</span> <span class="mi">1</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">.</span><span class="n">value</span></div>

    <span class="k">def</span> <span class="nf">_compress_immut</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">merge_threshold</span><span class="p">):</span>
        <span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span>

        <span class="n">res</span> <span class="o">=</span> <span class="p">[]</span>

        <span class="c1"># Start from the last element</span>
        <span class="n">head</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span>
        <span class="n">i</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">)</span> <span class="o">-</span> <span class="mi">2</span>  <span class="c1"># Do not merge the last element</span>

        <span class="k">while</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">1</span><span class="p">:</span>
            <span class="n">this_sample</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>
            <span class="k">if</span> <span class="n">this_sample</span><span class="o">.</span><span class="n">g</span> <span class="o">+</span> <span class="n">head</span><span class="o">.</span><span class="n">g</span> <span class="o">+</span> <span class="n">head</span><span class="o">.</span><span class="n">delta</span> <span class="o">&lt;</span> <span class="n">merge_threshold</span><span class="p">:</span>
                <span class="n">head</span><span class="o">.</span><span class="n">g</span> <span class="o">=</span> <span class="n">head</span><span class="o">.</span><span class="n">g</span> <span class="o">+</span> <span class="n">this_sample</span><span class="o">.</span><span class="n">g</span>
            <span class="k">else</span><span class="p">:</span>
                <span class="n">res</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">head</span><span class="p">)</span>
                <span class="n">head</span> <span class="o">=</span> <span class="n">this_sample</span>
            <span class="n">i</span> <span class="o">-=</span> <span class="mi">1</span>
        <span class="n">res</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">head</span><span class="p">)</span>

        <span class="c1"># If head of current sample is smaller than this new res&#39;s head</span>
        <span class="c1"># Add current head into res</span>
        <span class="n">current_head</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
        <span class="k">if</span> <span class="n">current_head</span><span class="o">.</span><span class="n">value</span> <span class="o">&lt;=</span> <span class="n">head</span><span class="o">.</span><span class="n">value</span> <span class="ow">and</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">sampled</span><span class="p">)</span> <span class="o">&gt;</span> <span class="mi">1</span><span class="p">:</span>
            <span class="n">res</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">current_head</span><span class="p">)</span>

        <span class="c1"># Python do not support prepend, thus, use reverse instead</span>
        <span class="n">res</span><span class="o">.</span><span class="n">reverse</span><span class="p">()</span>
        <span class="k">return</span> <span class="n">res</span></div>


<div class="viewcode-block" id="SparseQuantileSummaries"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.SparseQuantileSummaries">[docs]</a><span class="k">class</span> <span class="nc">SparseQuantileSummaries</span><span class="p">(</span><span class="n">QuantileSummaries</span><span class="p">):</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">compress_thres</span><span class="o">=</span><span class="n">consts</span><span class="o">.</span><span class="n">DEFAULT_COMPRESS_THRESHOLD</span><span class="p">,</span>
                 <span class="n">head_size</span><span class="o">=</span><span class="n">consts</span><span class="o">.</span><span class="n">DEFAULT_HEAD_SIZE</span><span class="p">,</span>
                 <span class="n">error</span><span class="o">=</span><span class="n">consts</span><span class="o">.</span><span class="n">DEFAULT_RELATIVE_ERROR</span><span class="p">,</span>
                 <span class="n">abnormal_list</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">SparseQuantileSummaries</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="fm">__init__</span><span class="p">(</span><span class="n">compress_thres</span><span class="p">,</span> <span class="n">head_size</span><span class="p">,</span> <span class="n">error</span><span class="p">,</span> <span class="n">abnormal_list</span><span class="p">)</span>

        <span class="c1"># Compare with the sparse point, static the number of each part.</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">smaller_num</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">bigger_num</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_total_count</span> <span class="o">=</span> <span class="mi">0</span>

<div class="viewcode-block" id="SparseQuantileSummaries.set_total_count"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.SparseQuantileSummaries.set_total_count">[docs]</a>    <span class="k">def</span> <span class="nf">set_total_count</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">total_count</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">_total_count</span> <span class="o">=</span> <span class="n">total_count</span></div>

<div class="viewcode-block" id="SparseQuantileSummaries.insert"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.SparseQuantileSummaries.insert">[docs]</a>    <span class="k">def</span> <span class="nf">insert</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">x</span> <span class="o">&lt;</span> <span class="n">consts</span><span class="o">.</span><span class="n">FLOAT_ZERO</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">smaller_num</span> <span class="o">+=</span> <span class="mi">1</span>
        <span class="k">elif</span> <span class="n">x</span> <span class="o">&gt;=</span> <span class="n">consts</span><span class="o">.</span><span class="n">FLOAT_ZERO</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">bigger_num</span> <span class="o">+=</span> <span class="mi">1</span>

        <span class="nb">super</span><span class="p">(</span><span class="n">SparseQuantileSummaries</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">insert</span><span class="p">(</span><span class="n">x</span><span class="p">)</span></div>

<div class="viewcode-block" id="SparseQuantileSummaries.query"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.SparseQuantileSummaries.query">[docs]</a>    <span class="k">def</span> <span class="nf">query</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">quantile</span><span class="p">):</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">zero_lower_bound</span> <span class="o">&lt;=</span> <span class="n">quantile</span> <span class="o">&lt;=</span> <span class="bp">self</span><span class="o">.</span><span class="n">zero_upper_bound</span><span class="p">:</span>
            <span class="k">return</span> <span class="mf">0.0</span>

        <span class="n">non_zero_quantile</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_convert_query_percentile</span><span class="p">(</span><span class="n">quantile</span><span class="p">)</span>
        <span class="n">result</span> <span class="o">=</span> <span class="nb">super</span><span class="p">(</span><span class="n">SparseQuantileSummaries</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="n">non_zero_quantile</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">result</span></div>

<div class="viewcode-block" id="SparseQuantileSummaries.merge"><a class="viewcode-back" href="../../../federatedml.feature.html#federatedml.feature.quantile_summaries.SparseQuantileSummaries.merge">[docs]</a>    <span class="k">def</span> <span class="nf">merge</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">smaller_num</span> <span class="o">+=</span> <span class="n">other</span><span class="o">.</span><span class="n">smaller_num</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">bigger_num</span> <span class="o">+=</span> <span class="n">other</span><span class="o">.</span><span class="n">bigger_num</span>
        <span class="nb">super</span><span class="p">(</span><span class="n">SparseQuantileSummaries</span><span class="p">,</span> <span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="n">merge</span><span class="p">(</span><span class="n">other</span><span class="p">)</span></div>

    <span class="k">def</span> <span class="nf">_convert_query_percentile</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">quantile</span><span class="p">):</span>
        <span class="n">zeros_count</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_total_count</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">count</span>
        <span class="k">if</span> <span class="n">zeros_count</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">return</span> <span class="n">quantile</span>

        <span class="k">if</span> <span class="n">quantile</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">zero_lower_bound</span><span class="p">:</span>
            <span class="k">return</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_total_count</span> <span class="o">/</span> <span class="bp">self</span><span class="o">.</span><span class="n">count</span><span class="p">)</span> <span class="o">*</span> <span class="n">quantile</span>

        <span class="k">return</span> <span class="p">(</span><span class="n">quantile</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">zero_upper_bound</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">zero_lower_bound</span><span class="p">)</span> <span class="o">/</span> <span class="p">(</span>
        <span class="mi">1</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">zero_upper_bound</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">zero_lower_bound</span><span class="p">)</span>

    <span class="nd">@property</span>
    <span class="k">def</span> <span class="nf">zero_lower_bound</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">smaller_num</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">return</span> <span class="mf">0.0</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">smaller_num</span> <span class="o">/</span> <span class="bp">self</span><span class="o">.</span><span class="n">_total_count</span>

    <span class="nd">@property</span>
    <span class="k">def</span> <span class="nf">zero_upper_bound</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">bigger_num</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
            <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_total_count</span>
        <span class="n">zeros_num</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_total_count</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">smaller_num</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">bigger_num</span>
        <span class="k">return</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">smaller_num</span> <span class="o">+</span> <span class="n">zeros_num</span><span class="p">)</span> <span class="o">/</span> <span class="bp">self</span><span class="o">.</span><span class="n">_total_count</span></div>
</pre></div>

           </div>
           
          </div>
          <footer>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; Copyright 2019, FATE_TEAM

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. 

</footer>

        </div>
      </div>

    </section>

  </div>
  


  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.Navigation.enable(true);
      });
  </script>

  
  
    
   

</body>
</html>